package adt.bst;

public class BSTImpl<T extends Comparable<T>> implements BST<T> {

	protected  BSTNode<T> root;
	
	
	public BSTImpl() {
		root = new BSTNode<T>();
	}

	public BSTNode<T> getRoot(){
		return this.root;
	}
	
	@Override
	public boolean isEmpty() {
		return root.isEmpty();
	}

	@Override
	public int height() {
		return height(root);
	}
	
	private int height(BSTNode<T> node) {
		if (node.isEmpty()) {
			return -1;
		} else {
			int hL = height((BSTNode<T>) node.getLeft());
			int hR = height((BSTNode<T>) node.getRight());
			if (hL < hR)
				return hR + 1;
			else
				return hL + 1;
		}
	}

	@Override
	public BSTNode<T> search(T element) {
		BSTNode<T> x = root;
		while(!x.isEmpty() && !(x.getData().equals(element))){
			if(x.getData().compareTo(element) < 0){
				x = (BSTNode<T>) x.getLeft();
			}else{
				x = (BSTNode<T>) x.getRight();
			}
		}
		return x;
	}

	@Override
	public void insert(T element) {
		if(root.isEmpty()){
			root = new BSTNode<T>();
			root.setData(element);
			root.setParent(null);
		}else{
			insert(root, element);
		}
	}
	
	public void insert(BSTNode<T> node, T element){
		if(element.compareTo(node.getData()) < 0){
			if(node.getLeft().isEmpty()){
			    node.setLeft(new BSTNode<T>());
			    node.getLeft().setParent(node);
			}else{
				insert((BSTNode<T>) node.getLeft(), element);
			}
		}
		else if(element.compareTo(node.getData()) < 0){
			if(node.getRight().isEmpty()){
			    node.setRight(new BSTNode<T>());
			    node.getRight().setParent(node);
			}else{
				insert((BSTNode<T>) node.getRight(), element);
			}
		}
	
		
	}

	@Override
	public BSTNode<T> maximum() {
		BSTNode<T> x = root;
		while(!x.getRight().isEmpty()){
			x = (BSTNode<T>) x.getRight();
		}
		return x;
	}
	
	public BSTNode<T> maximum(T element) {
		BSTNode<T> x = search(element);
		while(!x.getRight().isEmpty()){
			x = (BSTNode<T>) x.getRight();
		}
		return x;
	}

	@Override
	public BSTNode<T> minimum() {
		BSTNode<T> x = root;
		while(!x.getLeft().isEmpty()){
			x = (BSTNode<T>) x.getLeft();
		}
		return x;
	}
	
	public BSTNode<T> minimum(T element) {
		BSTNode<T> x = search(element);
		while(!x.getLeft().isEmpty()){
			x = (BSTNode<T>) x.getLeft();
		}
		return x;
	}
	

	@Override
	public BSTNode<T> sucessor(T element) {
		BSTNode<T> x = search(element);
		if(!x.getRight().isEmpty()){
			return minimum(x.getRight().getData());
		}
		BSTNode<T> y = search(element);
		while(!y.isEmpty() && x.equals(y.getRight())){
			x = y;
			y = (BSTNode<T>) y.getParent();
		}
		return y;
	}

	@Override
	public BSTNode<T> predecessor(T element) {
		BSTNode<T> x = search(element);
		if(!x.getLeft().isEmpty()){
			return maximum(x.getLeft().getData());
		}
		BSTNode<T> y = (BSTNode<T>) x.getParent();
		while(!y.isEmpty() && x.equals(y.getLeft())){
			x = y;
			y = (BSTNode<T>) y.getParent();
		}
		return y;
	}

	@Override
	public void remove(T element) {
		// TODO Auto-generated method stub

	}
	

	@Override
	public T[] preOrder() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public T[] order() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public T[] postOrder() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public int size() {
		return size(root);
	}
	private int size(BSTNode<T> node){
		int result = 0;
		if(!node.isEmpty()){
			result = 1 + size((BSTNode<T>)node.getLeft()) + size((BSTNode<T>)node.getRight());
		}
		return result;
	}

}
